#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXLEN 16384

char hold[MAXLEN] = "";
char file_in[MAXLEN] = "";
char file_out[MAXLEN] = "";

// 关键字
char* keywords[] = {
    "int",
    "return",
};
char* keywordsToken[] = {
    "Int",
    "Return",
};

// 算符优先分析
enum operator { Plus, Minus, Mult, Div, Rem, LPar, RPar, UnPlus, UnMinus, Number, Boundary };
enum operator operators[MAXLEN];
int top_opt = -1;
int numbers[MAXLEN];
int registers[MAXLEN];
int top_num = -1;
/*  0 : = 
    1 : < 
    2 : >
    3 : error */
int priority[11][11] = {
    {2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2},  // '+'
    {2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2},  // '-'
    {2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 2},  // '*'
    {2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 2},  // '\'
    {2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 2},  // '%'
    {1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 3},  // '('
    {2, 2, 2, 2, 2, 3, 2, 3, 3, 3, 2},  // ')'
    {2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 2},  // '\+'
    {2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 2},  // '\-'
    {2, 2, 2, 2, 2, 3, 2, 3, 3, 3, 2},  // 'i'
    {1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3},  // '#'
};
int num_register = 0;

void annotationElimination(char *file_input, char *file_output);
void lexicalAnalysis(char *file_input, char *file_output);
void syntaxAnalysis(char *file_input, char *file_output);

int isBlank(char c) {
    return c == ' ' || c == '\t' || c == '\n' || c == '\v' || c == '\r' || c == '\f'; 
}

int isDigit(char c) {
    return c >= '0' && c <= '9'; 
}
int isNonZeroDigit(char c) {
    return c >= '1' && c <= '9';
}
int isOctalDigit(char c) {
    return c >= '0' && c <= '7';
}
int isHexDigit(char c) {
    return c >= '0' && c<= '9' || c >= 'a' && c <= 'f' || c >= 'A' && c <= 'F';
}
int isLetter(char c) {
    return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'; 
}
int isUnderLine(char c) {
    return c == '_'; 
}
char* FindKeywords(char str[]) {
    int i;
    // printf("====%d====\n", sizeof(keywords) / sizeof(keywords[0]));
    for (i=0; i<sizeof(keywords)/sizeof(keywords[0]); i++) {
        if (strcmp(keywords[i], str) == 0) {
            // printf("====%s====\n", keywordsToken[i]);
            return keywordsToken[i];
        }
    }
    return "";
}

int isFuncDefBegin(char str[]) {
    return (strcmp(str, "Int") == 0);
}
void slice(char str[], int start, int end) {
    char temp[MAXLEN];
    memset(temp, '\0', sizeof(temp));
    for (int i=start; i<=end; i++) {
        temp[i-start] = str[i];
    }
    memset(hold, '\0', sizeof(hold));
    for (int i=0; i<strlen(temp); i++) {
        hold[i] = temp[i];
    }
}
int isNumber(char arr[]) {
    return strncmp(hold, "DecNumber", 9)==0 || strncmp(hold, "OctNumber", 9)==0 || strncmp(hold, "HexNumber", 9)==0;
}
int D2D(char arr[]) {
    int temp = 0;
    for(int i=0; i<strlen(arr); i++) {
        temp = temp * 10 + arr[i] - '0';
    }
    return temp;
}
int O2D(char arr[]) {
    int temp = 0;
    for(int i=0; i<strlen(arr); i++) {
        temp = temp * 8 + arr[i] - '0';
    }
    return temp;
}
int H2D(char arr[]) {
    int temp = 0;
    for(int i=0; i<strlen(arr); i++) {
        if (arr[i]>='0' && arr[i] <= '9')
            temp = temp * 16 + arr[i] - '0';
        else if (arr[i]>='a' && arr[i] <='f') {
            temp = temp * 16 + arr[i] - 'a' + 10;
        }
        else {
            temp = temp * 16 + arr[i] - 'A' + 10;
        }   
    }
    return temp;
}
void analyseFuncDef(FILE *fp_in, FILE *fp_out);
void analyseStmt(FILE *fp_in, FILE *fp_out);
void analyseBlock(FILE *fp_in, FILE *fp_out);
void analyseExp(FILE *fp_in, FILE *fp_out);
enum operator judgeOpt(char str[], enum operator pre);
void specify(FILE *fp_out);
void printLLVM(FILE *fp_out, char *str, int a, int b);
void printLLVM_(FILE *fp_out, char *str, int a, int b);

int main(int argc, char *argv[]) {
    memset(file_in, '\0', sizeof(file_in));
    memset(file_out, '\0', sizeof(file_out));
    if (argc < 2) {
        printf("Wrong parameter!\n");
        exit(-1);
    } else {
        strcpy(file_in, argv[1]);
        strcpy(file_out, argv[2]);
    }

    // 消除注释
    annotationElimination(file_in, "no_comment.txt");
    // 词法分析
    lexicalAnalysis("no_comment.txt", "lex.txt");
    // 语法分析
    syntaxAnalysis("lex.txt", file_out);

    return 0;
}

void annotationElimination(char *file_input, char *file_output) {
    // 打开文件
    FILE *fp_in, *fp_out;
    if ((fp_in = fopen(file_input, "r")) == NULL) {
        printf("File open error!\n");
        exit(-1);
    }
    if ((fp_out = fopen(file_output, "w")) == NULL) {
        printf("File open error!\n");
        exit(-1);
    }

    // 循环读入处理
    char ch;
    while(1) {
        // 读入
        ch = fgetc(fp_in);

        // 文件结束判断
        if (ch == EOF) {
            break;
        }

        // 注释判断
        else if (ch == '/') {
            ch = fgetc(fp_in);
            // 单行注释
            if (ch == '/') {
                while(((ch = fgetc(fp_in)) != '\n') && ch != EOF);
                fputc('\n', fp_out);
            }
            // 多行注释
            else if (ch == '*') {
                while (1) {
                    while((ch = fgetc(fp_in)) != '*' && ch != EOF);
                    if (ch == EOF) {
                        break;
                    } else {
                        ch = fgetc(fp_in);
                        if (ch == '/') {
                            break;
                        } else {
                            ungetc(ch, fp_in);
                        }
                    }
                }
            }
            // 其他字符
            else {
                fputc('/', fp_out);
                fputc(ch, fp_out);
            } 
        }
        
        // 其他字符
        else {
            fputc(ch, fp_out);
        }
    }

    // 关闭文件
    fclose(fp_in);
    fclose(fp_out);
}

void lexicalAnalysis(char *file_input, char *file_output) {
    // 打开文件
    FILE *fp_in, *fp_out;
    if ((fp_in = fopen(file_input, "r")) == NULL) {
        printf("File open error!\n");
        exit(-1);
    }
    if ((fp_out = fopen(file_output, "w")) == NULL) {
        printf("File open error!\n");
        exit(-1);
    }

    // 读入分析
    char ch;
    memset(hold, '\0', sizeof(hold));
    while(1) {
        // 跳过空白字符
        while (isBlank(ch = fgetc(fp_in)));

        // 文件结束判断
        if (ch == EOF) {
            break;
        }

        // 数字判断
        else if (isDigit(ch)) {
            // 十进制
            if (isNonZeroDigit(ch)) {
                hold[0] = ch;
                for (int i=1; isDigit(ch = fgetc(fp_in)); i++) {
                    hold[i] = ch;
                }
                fprintf(fp_out, "DecNumber(%s)\n", hold);
                memset(hold, '\0', sizeof(hold));     // 重置hold
                ungetc(ch, fp_in);
            }
            // 八进制或十六进制
            else {
                ch = fgetc(fp_in);
                // 十六进制
                if (ch == 'x' || ch == 'X') {
                    char temp = ch;
                    for (int i=0; isHexDigit(ch = fgetc(fp_in)); i++) {
                        hold[i] = ch;
                    }
                    if (!isHexDigit(hold[0])) {
                        // 非十六进制数
                        fprintf(fp_out, "OctNumber(0)\n");
                        ungetc(ch, fp_in);
                        ungetc(temp, fp_in);
                    }
                    else {
                        fprintf(fp_out, "HexNumber(%s)\n", hold);
                        memset(hold,'\0',sizeof(hold));     // 重置hold
                        ungetc(ch, fp_in);
                    }
                }
                // 八进制
                else if (isOctalDigit(ch)) {
                    hold[0] = ch;
                    for (int i=1; isOctalDigit(ch = fgetc(fp_in)); i++) {
                        hold[i] = ch;
                    }
                    fprintf(fp_out, "OctNumber(%s)\n", hold);
                    memset(hold,'\0',sizeof(hold));     // 重置hold
                    ungetc(ch, fp_in);
                } 
                // 零和其他
                else {
                    fprintf(fp_out, "OctNumber(0)\n");
                    ungetc(ch, fp_in);
                }
            }
        }

        // 标识符(关键字)判断
        else if (isLetter(ch) || isUnderLine(ch)) {
            hold[0] = ch;
            for (int i=1; isDigit(ch = fgetc(fp_in)) || isLetter(ch) || isUnderLine(ch); i++) {
                hold[i] = ch;
            }
            char token[128];
            memset(token, '\0', sizeof(token));
            // 关键字判断
            strcpy(token, FindKeywords(hold));
            if ((strcmp(token, "")) != 0) {
                fprintf(fp_out, "%s\n", token);
            }
            else {
               fprintf(fp_out, "Ident(%s)\n", hold);
            }
            memset(hold, '\0', sizeof(hold));     // 重置hold
            ungetc(ch, fp_in);
        }

        // 特殊符号判断
        else if (ch == ';') {
            fprintf(fp_out, "Semicolon\n");
        }
        else if (ch == '(') {
            fprintf(fp_out, "LPar\n");
        }
        else if (ch == ')') {
            fprintf(fp_out, "RPar\n");
        }
        else if (ch == '{') {
            fprintf(fp_out, "LBrace\n");
        }
        else if (ch == '}') {
            fprintf(fp_out, "RBrace\n");
        }
        else if (ch == '+') {
            fprintf(fp_out, "Plus\n");
        }
        else if (ch == '-') {
            fprintf(fp_out, "Minus\n");
        }
        else if (ch == '*') {
            fprintf(fp_out, "Mult\n");
        }
        else if (ch == '/') {
            fprintf(fp_out, "Div\n");
        }
        else if (ch == '%') {
            fprintf(fp_out, "Rem\n");
        }

        // 词法错误
        else {
            exit(1);
        }
    }
    
    // 关闭文件
    fclose(fp_in);
    fclose(fp_out);
}

void syntaxAnalysis(char *file_input, char *file_output) {
    // 打开文件
    FILE *fp_in, *fp_out;
    if ((fp_in = fopen(file_input, "r")) == NULL) {
        printf("File open error!\n");
        exit(-1);
    }
    if ((fp_out = fopen(file_output, "w")) == NULL) {
        printf("File open error!\n");
        exit(-1);
    }
    
    // 逐行读入语法分析
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);
    while(strlen(hold) != 0) {
        // CompUnit语法判断
        if (isFuncDefBegin(hold)) {
            analyseFuncDef(fp_in, fp_out);
        }

        // 语法错误
        else {
            exit(2);
        }
    }

    // 关闭文件
    fclose(fp_in);
    fclose(fp_out);
}

void analyseFuncDef(FILE *fp_in, FILE *fp_out) {
    // FuncType
    if (strcmp(hold, "Int") == 0) {
        fprintf(fp_out, "define dso_local i32 ");
    } else {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);

    // Ident
    if (strncmp(hold, "Ident", 5) == 0) {
        slice(hold, 6, strlen(hold)-2);
        fprintf(fp_out, "@%s ", hold);
    } else {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);

    // '('
    if (strcmp(hold, "LPar") == 0 ) {
        fprintf(fp_out, "(");
    } else {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);

    // ')'
    if (strcmp(hold, "RPar") == 0 ) {
        fprintf(fp_out, ")");
    } else {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);

    // Block
    analyseBlock(fp_in, fp_out);
}

void analyseBlock(FILE *fp_in, FILE *fp_out) {
    // '{'
    if (strcmp(hold, "LBrace") == 0 ) {
        fprintf(fp_out, "{\n");
    } else {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);
    
    // Stmt
    analyseStmt(fp_in, fp_out);

    // '}'
    if (strcmp(hold, "RBrace") == 0 ) {
        fprintf(fp_out, "}");
    } else {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);
}

void analyseStmt(FILE *fp_in, FILE *fp_out) {
    // return
    if (strcmp(hold, "Return") != 0) {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    // fscanf(fp_in, "%s", hold);

    // Exp
    analyseExp(fp_in, fp_out);
    fprintf(fp_out, "\tret i32 %%x%d\n", num_register-1);

    // ';'
    if (strcmp(hold, "Semicolon") != 0) {
        exit(2);   // 语法错误
    }
    memset(hold, '\0', sizeof(hold));
    fscanf(fp_in, "%s", hold);
}

void analyseExp(FILE *fp_in, FILE *fp_out) {
    // 初始化
    memset(operators, 0, sizeof(operators));
    memset(numbers, 0, sizeof(numbers));
    memset(registers, -1, sizeof(registers));
    operators[++top_opt] = Boundary;
    num_register = 0;
    int flag_read = 1;   // 循环是否需要新读入 
    enum operator opt = Boundary;
    
    // 循环处理
    while (1) {
        // 读入字符
        if (flag_read) {
            fscanf(fp_in, "%s", hold);
            enum operator pre = opt;
            opt = judgeOpt(hold, pre);
            if (pre == Number && (opt == Number || opt == LPar)) {
                printf("wrong priority");
                exit(2);
            }
        }
        // 分析结束
        if (opt == Boundary && operators[top_opt] == Boundary && top_num != -1) {
            printf("over: %d\n", numbers[top_num]);
            break;
        }
        // 优先级等于
        else if (priority[operators[top_opt]][opt] == 0) {
            if (top_num == -1 || operators[top_opt] != LPar) {
                printf("parenthesis error");
                exit(2);    // 语法错误
            }
            top_opt--;
            flag_read = 1;
        }
        // 优先级小于
        else if (priority[operators[top_opt]][opt] == 1) {
            if (opt == Number) {
                if (strncmp(hold, "Dec", 3) == 0) { 
                    slice(hold, 10, strlen(hold)-2); 
                    numbers[++top_num] = D2D(hold); 
                }
                if (strncmp(hold, "Oct", 3) == 0) { 
                    slice(hold, 10, strlen(hold)-2);
                    numbers[++top_num] = O2D(hold); 
                }
                if (strncmp(hold, "Hex", 3) == 0) {
                    slice(hold, 10, strlen(hold)-2); 
                    numbers[++top_num] = H2D(hold); 
                }           
            } else {
                operators[++top_opt] = opt;
            }
            flag_read = 1;
        }
        // 优先级大于
        else if (priority[operators[top_opt]][opt] == 2) {
            specify(fp_out);
            flag_read = 0;
        }
        // 出错
        else if (priority[operators[top_opt]][opt] == 3) {
            printf("wrong priority\n");
            exit(2);    // 语法错误
        }
    }
}

enum operator judgeOpt(char str[], enum operator pre) {
    if (strcmp(str, "Plus") == 0) {
        if (pre == Number || pre == RPar) {
            return Plus;
        } else {
            return UnPlus;
        }
    }
    if (strcmp(str, "Minus") == 0) {
        if (pre == Number || pre == RPar) {
            return Minus;
        } else {
            return UnMinus;
        }
    }
    if (strcmp(str, "Mult") == 0) { return Mult; }
    if (strcmp(str, "Div") == 0) { return Div; }
    if (strcmp(str, "Rem") == 0) { return Rem; }
    if (strcmp(str, "LPar") == 0) { return LPar; }
    if (strcmp(str, "RPar") == 0) { return RPar; }
    if (isNumber(hold)) { return Number; }
    return Boundary;
}


void specify(FILE *fp_out) {
    enum operator opt = operators[top_opt--];

    // 双目运算
    if (opt != UnPlus && opt != UnMinus) {
        // 运算数不够
        if (top_num < 1) {
            printf("nums not enough(bi)\n");
            exit(2);    // 语法错误 
        }
        // 运算
        int b = numbers[top_num--];
        int a = numbers[top_num--];
        if (opt == Plus) { 
            numbers[++top_num] = a + b;
            printLLVM(fp_out, "add", a, b);
        }
        if (opt == Minus) { 
            numbers[++top_num] = a - b; 
            printLLVM(fp_out, "sub", a, b);
        }
        if (opt == Mult) { 
            numbers[++top_num] = a * b; 
            printLLVM(fp_out, "mul", a, b);
        }
        if (opt == Div) { 
            numbers[++top_num] = a / b;
            printLLVM(fp_out, "sdiv", a, b);
        }
        if (opt == Rem) { 
            numbers[++top_num] = a % b; 
            printLLVM(fp_out, "srem", a, b);
        }
    }

    // 单目运算
    else {
        // 运算数不够
        if (top_num == -1) { 
            printf("nums not enough(un)\n"); 
            exit(2);    // 语法错误 
        }
        // 运算
        int a = numbers[top_num--];
        if (opt == UnPlus) { 
            numbers[++top_num] = a;
        }
        if (opt == UnMinus) { 
            numbers[++top_num] = -a;
            fprintf(fp_out, "\t%%x%d = sub i32 0, %d\n", num_register, a);
            registers[top_num] = num_register++;
            registers[top_num+1] = -1; 
        }
    }
}

void printLLVM(FILE *fp_out, char *str, int a, int b) {
    // i & i
    if (registers[top_num] == -1 && registers[top_num+1] == -1) {
        fprintf(fp_out, "\t%%x%d = %s i32 %d, %d\n", num_register, str, a, b);
    }
    // %i & i
    if (registers[top_num] != -1 && registers[top_num+1] == -1) {
        fprintf(fp_out, "\t%%x%d = %s i32 %%x%d, %d\n", num_register, str, registers[top_num], b);
    }
    // i & %i
    if (registers[top_num] == -1 && registers[top_num+1] != -1) {
        fprintf(fp_out, "\t%%x%d = %s i32 %d, %%x%d\n", num_register, str, a, registers[top_num+1]); 
    }
    // %i & %i
    if (registers[top_num] != -1 && registers[top_num+1] != -1) {
        fprintf(fp_out, "\t%%x%d = %s i32 %%x%d, %%x%d\n", num_register, str, registers[top_num], registers[top_num+1]);   
    }
    registers[top_num] =  num_register++;
    registers[top_num+1] = -1;
}